Mars
0%

Grokking Algorithms

发表于 更新于 分类于 ，

对算法的了解一直很肤浅（听学数学的朋友说算法在数学中也叫数论？），本书阅读不求快，本就是入门读物，希望能尽量理解，争取早日拿下。

这边值得一提的是作者推荐了一个网站，可汗学院，khanacademy.org mark一下。

看完40%来总结一下，非常好，文盲也能看懂的算法入门。

这本书看完应该会扫一眼结城浩的《图解密码学》

第一章 算法简介

1.1 引言

好的，我具备了

1.2 二分查找

二分查找(binary search)又叫折半搜索(half-interval search)、对数搜索(logarithmic search)，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

对数：幂运算的逆运算

假设你要在字典中查找一个单词，而该字典包含240000个单词，
你认为每种查找最多需要多少步？

log2 n步，本题中就是18步

给定一个有序数组和一个需要定位的数字，先创建两个变量 low 和 high，low和high一开始分别是数组的第一个和最后一个坐标，划定一个取中间元素的空间，然后取出中间元素和目标元素比较，如果不是的话，就更改low或者high中某一个的坐标为(low + high)/2，将查找空间缩小为原来的二分之一，然后继续。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binary_search(list, item):
  low = 0
  high = len(list) - 1
  
  while low <= high:
    mid = (low + high) // 2
    guess = list[mid]
    if guess == item:
      return mid
    if guess > item:
      high = mid -1
    else:
      low = mid + 1
  return None

my_list = [1,3,5,7,9]

print binary_search(my_list, 3)
print binary_search(my_list, -1)

运行环境

Tips：关于为什么更换搜索区域的时候没有直接用high = mid 或者low = mid

注意while的条件，如果没有这一条，范围缩小到两个数的时候，会无限循环

运行时间

最多猜测次数与列表长度相同被称为线性时间(linear time).

二分查找的运行时间为对数时间(log time).

1.3 大 O 表示法

1
2
3
4
5
6
O(1):             常量时间，哈希
O(log2(n)):       对数时间，二分，
O(n):             线性时间，简单
O(nlog2(n)):              快速排序
O(n2):                    选择排序（冒泡）
O(n!):                    旅行商问题

算法的速度指的并非时间，而是操作数的增速。

谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

算法的运行时间用大O表示法表示。

O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

旅行商问题

行商问题（最短路径问题）（英语：travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。

第二章 选择排序

2.1 内存工作原理

2.2 数组和链表

链表：不需要移动元素，优势在插入元素

使用链表在中间插入元素只需要修改前面一个元素指向的地址，因此当需要在中间插入的时候，链表是更好的选择。

删除也是一样

数组和链表的运行时间：

数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

有两种访问方式：随机访问和顺序访问。

顺序访问意味着从第一个元素开始逐个读取元素，链表只能顺序访问，数组支持随机访问，所以数组在需要随机访问的情况下用得很多。

2.3 选择排序

时间复杂度的Tips

1
2
3
4
5
6
7
8
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1,len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
1
2
3
4
5
6
7
8
def selection(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print(selection( [5,3,6,2,10] ))

Tips：

python之间的语法不兼容是很蛋疼的事情

py2：

1
print "Pyhon 2 can use print string without ()";

py3:

1
print("Python3, print must use () to output string");

py3中，print作为函数必须要带括号

第三章 递归

递归：优雅的问题解决办法

3.1 递归

“如果使用循环，程序的性能可能更高；如果使用递归，程序可能 更容易理解。如何选择要看什么对你来说更重要“

3.2 基线条件和递归条件

递归条件(base case)是指函数调用自己，基线条件(recursive case)是指函数不再调用自己，从而表面形成无限循环。

1
2
3
4
5
6
7
8
def countdown(i):
    print(i)
    if i <= 0:
        return
    else:
        countdown(i-1)

countdown(10)

3.3 栈

调用栈（call stack）

python虽然不是用的JVM 但是 对于栈内存的调用 好像都差不多

递归函数factorial(5)写作5!

意义是5! = 5 * 4 * 3 * 2 * 1

使用栈虽然很方便但是也要付出代价：占用大量内存

第四章 快速排序

4.1 分而治之

一种著名的递归式问题解决方法—divide and conquer,D&C

重要的D&C是算法：快排，优雅代码的典范

欧几里得算法(辗转相除法)：gcd(a.b) = gcd(b, a%b)

大的那个数 小的那个数 余数 商
a b r0 = a%b q0
b r0 r1 = b% r0 q1
r0 r1 r2 = r0 % r1 q2
… … … …
rN-4 rN-3 rN-2 = rN-4 % rN-3 qN-2
rN-3 rN-2 rN-1 = rN-3 % rN-2 qN-1
rN-2 rN-1 rN = rN-2 % rN-1 qN
rN-1 rN == 0 rN-1 = 1 * rN-1 - 0 * rN 0

得到的最大公约数就是rN-1

欧几里得算法的证明：

我个人觉得反证法比较好理解：

要证欧几里德算法成立，即证: gcd(a,b)=gcd(b,r),其中 gcd是取最大公约数的意思，r=a mod b
下面证 gcd（a，b）=gcd（b，r）
设 c是a，b的最大公约数，即c=gcd（a，b），则有 a=mc，b=nc，其中m，n为正整数，且m，n互为质数
由 r= a mod b可知，r= a- qb 其中，q是正整数，
则 r=a-qb=mc-qnc=（m-qn）c
b=nc,r=(m-qn)c，且n，（m-qn）互质（假设n，m-qn不互质，则n=xd, m-qn=yd 其中x,y,d都是正整数，且d>1

​ 则a=mc=(qx+y)dc, b=xdc,这时a,b 的最大公约数变成dc，与前提矛盾，所以n ，m-qn一定互质）
​ 则gcd（b,r）=c=gcd（a,b）
​ 得证。

编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时， 请检查基线条件是不是这样的。

4.2 快排

快排使用了D&C

思路：

基线条件：数组为空或者只包含一个元素。这种情况下，只需要原样返回。

对于两个元素的数组：如果第一个元素比第二个元素小，直接返回，如果不是，就交换位置。

三个元素的数组：

从数组中选择一个元素，这个元素被称为基准值(pivot)，

我们暂时先将数组的第一个元素作为基准值。

接下来找出比基准值小的元素以及比他大的元素。这个过程被称为分区（partition）

这里两个分区出来的数组时无需的，但是如果这两个数组是有序的，对整个数组进行排序将非常容易。

那么问题就转化成了如何对子数组进行排序，

这里我们讨论的是特定情况（三个元素），无论选用哪个元素作为pivot，剩下的情况总能用上面两个元素数组的排序方法代入。

于是就得到了解决办法

接下来四个元素的情况，类似的。

1
2
3
4
5
6
7
8
9
10
11
12
13
def quicksort(array):
    # 基线条件
    if len(array) < 2:
        return array
    else:
        # 递归条件
        pivot = array[0]
        # 分为两个数组
        less = [ i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([1,6,3,5,7,4,2,45645,34,23,65,1]))

这边可以对比一下时间复杂度

选择排序的时间复杂度是O(n2)

快速排序的时间复杂度最差是O(n2)，平均情况是O(n log n)

还有一种合并排序(merge sort)运行时间是O(n log n)

现在做出一个有趣的假设，假设简单查找每次需要10ms，二分查找的常量是1s，现在我们假设查找的元素个数是10个，简单查找需要100ms，二分查找却需要log 10 * 1s，可以二分查找的时间远大于简单查找，但是我们查找的元素很大时，比如40亿，这个时候我们使用简单查找需要463天，但是二分查找只要32s。

通过这个例子，我们可以看到常量的影响可能会很大。

我们再来看快排，快排的效率取决于选择的pivot，当pivot是最小值的时候，我们其实只用到的一个数组，要递归很多次才能递归结束，这种情况是最坏的情况

如果我们选择的是中间值，是最佳情况，这种情况下根本不要这么多递归，因此调用栈就短得多。

需要注意的是，我们并不是如图这么简单的+n次调用，作为递归二次每次调用栈都设计O(n)，这是递归的性质决定的。

因此，实际上最佳情况是O(n log n)

最佳情况也是平均情况（和最佳情况在同一数量级所以忽略掉前面的参数，剩下的相同），快排是D&G的典范。

第五章 散列表 Hash Table

散列表是足有用的基本数据结构之一。

虽然二分法的效率已经可以了，但是能不能有一种查找方法的查找时间是O(1)呢——任意给出一个查找内容，都能立即给出答案。

5.1 散列函数

散列函数应该满足的要求：

  • 他必须是一致的。例如：假设你输入apple时得到的是4，那么每次输入apple的时候，得到的都必须是4，如果不是这样，散列表将毫无用处。
  • 它应该将不同的输入映射到不同的数字，如果一个散列函数不管输入是什么都返回1就不可以。最理想的情况是，将不同的输入映射到不同的数字。

原理：

  • 散列函数总是将同样的输入映射到相同的索引。
  • 不同输入映射到不同的索引。
  • 散列函数知道数组有多大。

散列表是一种包含额外逻辑的数据结构。

散列表又被称为散列映射、映射、字典和关联数组。（Hash Table）

python提供的散列表实现为字典，可以使用dictt来创建散列表。

python语法中

book = dict()和book = {}等价。

5.2 应用案例

电话簿

DNS解析（域名关联IP）DNS resolution

防止重复（比如抽奖、投票）

将案列表用作缓存

Facebook将主页、about页面，Contact页面、Terms 和 Conditions页面等众多页面通过页面URL映射到页面数据。

5.3 冲突 collision

大多数语言都提供了散列实现，冲突是指，两个键分配的数组位置相同，这是个问题。

解决办法：如果两个键映射到了同一个位置，就在这个位置存储一个链表。

但是，如果A开头的物品过多，散列表的效率将激素下降，然而：如果散列函数用的很好，这些列表就不会很长。

5.4 性能

平均情况下，散列表的查找速度和数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但是最糟的情况下，散列表的各种操作都很慢。

因此，为了避免冲突，需要有：

较低的填装因子。

良好的散列函数。

装填因子：

散列表包含的元素数目/位置总数

假设再散列表中存储100种商品的价格，散列表包含100个位置名最佳情况下，每个商品都将有自己的位置。

装填因子在大于1的情况下，需要在散列表中添加位置，这个操作被称为**调整长度(resizing)**。

一般操作是：数组增加一倍。

接下来，将所有元素用hash函数插入到新的散列表中。

平均而言，即便考虑到调整长度所需的时间，散列表操作所需的 时间也为O(1)。

良好的散列函数让数组中的值呈均匀分布。

糟糕的散列函数让值扎堆，导致大量的冲突。

第六章 广度优先搜索

图算法之广度优先搜索 (breadth-first search)

6.1 图简介

如图用来解决从A点到B点最短路径问题的办法叫图计算方法。

这种最短路径既可能是最短路径，也有可能是国际象棋中将对方将死的最少步数。

解决最短路径问题的算法被称为广度优先搜索。

6.2 图是什么

图用于模拟不同的东西是如何相连的。

6.3 广度优先搜索

书中的例计较简单，在朋友圈中找A，先遍历朋友，查找是否有A，有的话结束，没有的话，依次遍历朋友的朋友。（和之前找芒果经销商是一样的）

能够实现这种目的的数据结构叫做队列（queue）

队列的工作原理：你不能随机访问队列中的元素。队列只支持两种操作：入队和出队。

队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。

6.4 实现图

python实现一个简单的图：

1
2
3
4
5
6
7
8
9
graph = {} 
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"] 
graph["alice"] = ["peggy"] 
graph["claire"] = ["thom", "jonny"] 
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = []

上图中的有向图和无向图是等价的。

6.5 实现算法

在Python中，可以使用函数deque来创建一个双端队列

这边需要考虑一个情况：就是朋友是朋友的朋友，循环调用会造成无限循环。

所以需要添加容错判断。用一个列表来记录检查过的人。

图的特殊情况：指针只往一个方向，比如说：族谱。

第七章 狄克斯特拉算法 Dijkstra’s Algorithm

7.1 狄克斯特拉算法介绍

依旧图的讨论。

如果之前的路径有了权重（节点到节点之间花费的时间不等价），重新计算最短路径，就应该使用狄克斯特拉算法。

狄克斯特拉算法包含四个步骤：

  • 找出最便宜的节点，即可在最短时间内前往的节点。
  • 对于该节点的邻居，检查是否有前往他们的最短路径，如果有，就更新其开销。
  • 重复这个过程，知道对图中的每个节点都这样做了。
  • 计算最终路径。

7.3 术语

每条边关联的数字叫做权重（weight）。

带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。

要计算非加权图中的最短路径，可以使用广度优先搜索。

如果是为了计算加权图中的最短路径，可以使用迪克斯特拉算法。

图还可能有环，这意味着你可以从一个节点出发，走一圈后又回到这个节点

在无向图中，每条边都是一个环，狄克斯特拉算法只使用于有向无环图（DAG）

7.4 负权边

如果有负权边就不能用，就不能使用狄克斯特拉算法，因为负权边，就不能使用狄克斯特拉算法。

因为负权边会导致这种算法不管用。

因为：根据狄克斯特拉算法，没有比不支付任何费用获得海报更便宜的方式。

因此：不能将狄克斯特拉算法用于包含负权边的图。

要在包含负权边的图中，找出最短路径，可以使用另一种算法： 贝尔曼—福德算法（Bellman-Ford algorithm）.

7.5 实现

可以用以上代码表示上图的散列表。

上面代码表达的表：

接下来需要一个散列表来粗春每个节点的开销。

节点的开销：从起点出发前往该节点需要的时间。

用表表示的话如图：

表中的无穷大可以这么表示：

python正负无穷

除了上面两张表，还需要一个存储父节点的散列表：

创建这个散列表的代码如下：

最后，需要一个数组用于记录处理过的节点，因为对于同一个节点，你不用处理多次。

1
processd = {}

动图表示整个认证过程：

整体过程：

本书介绍的python 迪克斯特拉算法：

使用了三个散列表和一个数组，三个散列表的作用分别是：

第一个：Graph散列表

用来记录每个节点到指向节点的权重

第二个：Costs散列表

指的起点到某个节点的消耗

第三个：Parents散列表

指的是父节点的散列表

数组的作用是记录用于处理过的节点。

处理过程是，

找出一个未处理的节点（规则定位开销最小的）

然后在表一获得该节点的开销和邻居。

遍历邻居，

接着计算从起点到X再到邻居节点的距离，然后在表一中对比这样的开销和原先的开销大小，如果这样效率更高，那么在表二中替换掉（或者更新掉原先的数字），然后在表三中改变其父节点为X

（表二记载的开销是经过父节点的最短开销）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
node = find_lowest_cost_node(costs)
while node is not None:
	cost = costs[node]
	neighbors = graph[node]
	for n in neighbors.keys():
		new_cost = cost + neighbors[n]
		if costs[n] > new_cost:
			costs[n] = new_cost
			parents[n] = node
	processed.append(node)
	node = find_lowest_cost_node(costs)
    
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
        	lowest_cost = cost
            lowest_cost_node = node
	return lowest_cost_node

书上对这个过程的描述还可以，但是我觉得如果能增加一个循环就更好了。

第八章 贪婪算法

8.1 教室调度问题

解决方法：

(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。

(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要 在这间教室上的第二堂课。

重读这样做就能找出答案。

即：每步都选择局部最优解，最终得到的就是全局最优解。

此方法并非万能！但是行之有效，并且简单！

8.2 背包问题